package review.Day_0508;

/**
 * @author zxc
 * @date 2023/05/08 21:21
 **/

/**
 * 题目 ：总持续时间能够被60整除的歌曲对数量
 * 题目详述 ：
 * 在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
 *
 * 返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。
 * 形式上，我们希望下标数字 i 和 j 满足 i < j 且有(time[i] + time[j]) % 60 == 0。
 *
 * 提示：
 * 1 <= time.length <= 6 * 104
 * 1 <= time[i] <= 500
 *
 */
public class NumPairsDivisibleBy60 {
    // 1.暴力法 ：即，固定住某个歌曲后，遍历该歌曲后的所有歌曲，来判断该歌曲对是否是60的倍数;
//    public int numPairsDivisibleBy60(int[] time) {
//        int len = time.length;
//        int number = 0;
//        for(int i = 0; i < len - 1; i++){
//            for(int j = i + 1; j < len; j++){
//                if((time[i] + time[j]) % 60 == 0){
//                    number++;
//                }
//            }
//        }
//        return number;
//    }

    // 2.统计time数组中，各个余数的歌曲对数;
    // 由于每首歌曲的余数都是固定的，所以可以根据余数，来统计不同余数歌曲数量，
    // 同时，使得 余数为 i && 余数为 60-i的歌曲数目，构成总时间为 60倍数的歌曲对;
    public int numPairsDivisibleBy60(int[] time) {
        int[] temp = new int[60];
        int result = 0;
        // 统计不同余数的歌曲数量;
        for (int i : time) {
            temp[i % 60]++;
        }
        //（1）遍历余数在0~29之间，来获取与之对应的60-i;
        for(int i = 1 ; i < 30 ; i++){
            result += temp[i] * temp[60 - i];
        }
        //（2）考虑特殊情况 ：余数为0 && 余数为30;
        result += (long)temp[0] * (temp[0] - 1) / 2 + (long)temp[30] * (temp[30] - 1) / 2;
        return result;
    }
}
